import java.util.LinkedList;
import java.util.Queue;

class BinaryTree {
    public static class BTNode {
        BTNode left;
        BTNode right;
        int value;

        BTNode(int value) {
            this.value = value;
        }
    }

    private BTNode root;

    public void createBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        BTNode node7 = new BTNode(6);
        BTNode node8 = new BTNode(6);
        BTNode node9 = new BTNode(6);
        BTNode node10 = new BTNode(6);
        root = node1;

        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        node4.right=node8;
        node4.left=node9;

    }


    void preOrder(BTNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);


    }

    void inOrder(BTNode root) {
        if (root == null) {
            return;
        }


        inOrder(root.left);

        System.out.print(root.value + " ");


        inOrder(root.right);


    }


    void postOrder(BTNode root) {
        if (root == null) {
            return;
        }


        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");


    }


    // 获取树中节点的个数
    int size(BTNode root) {
        if (root == null) {
            return 0;
        }

        return size(root.left) + size(root.right) + 1;

    }

    // 获取叶子节点的个数
    int getLeafNodeCount(BTNode root) {

        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return 1;
        }

        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);

    }

    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数


    int getKLevelNodeCount(BTNode root, int k) {

        if (root == null||k<1) {
            return 0;
        }

        if (k == 1) {
            return 1;
        }


        return getKLevelNodeCount(root.left, k - 1)+getKLevelNodeCount(root.right, k - 1);


    }

    // 获取二叉树的高度
    int getHeight(BTNode root) {

        if (root == null) {
            return 0;
        }

        int n1 = getHeight(root.left) + 1;
        int n2 = getHeight(root.right) + 1;

        return n1 > n2 ? n1 : n2;


    }

    // 检测值为value的元素是否存在
    BTNode find(BTNode root, int val) {

        if (root == null) {
            return root;
        }

        if (root.value == val) {
            return root;
        }

        BTNode n1 = find(root.left, val);
        BTNode n2 = find(root.right, val);

        if (n1 != null) {
            return n1;
        } else if (n2 != null) {
            return n2;
        }

        return null;


    }

    //层序遍历
    void levelOrder(BTNode root) {

        if (root == null) {
            return;
        }

        Queue<BTNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            BTNode node = queue.poll();
            System.out.print(node.value + " ");

            if (node.left != null) {
                queue.add(node.left);


                if (node.right != null) {
                    queue.add(node.right);
                }
            }

        }


    }

         // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(BTNode root) {
        if (root == null) {
            return true;
        }

        Queue<BTNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            BTNode node = queue.poll();

            if(node==null) {
                break;
            }


                queue.add(node.left);
                queue.add(node.right);

        }

        while (!queue.isEmpty()){
            BTNode node=queue.poll();
            if(node!=null){
                return false;
            }
        }

            return true;
    }








    public static void main(String[] args) {

        BinaryTree binaryTree=new BinaryTree();
        binaryTree.createBinaryTree();
        binaryTree.preOrder(binaryTree.root);
        System.out.println();
//        binaryTree.inOrder(binaryTree.root);
//        System.out.println();
//        binaryTree.postOrder(binaryTree.root);
//        System.out.println();

        System.out.println(binaryTree.size(binaryTree.root));
        System.out.println(binaryTree.getHeight(binaryTree.root));
        System.out.println(binaryTree.getLeafNodeCount(binaryTree.root));
        System.out.println(binaryTree.getKLevelNodeCount(binaryTree.root,4));
        System.out.println(binaryTree.getKLevelNodeCount(binaryTree.root,2));
        System.out.println(binaryTree.find(binaryTree.root,4).value);


        binaryTree.levelOrder(binaryTree.root);
        System.out.println();
        System.out.println(binaryTree.isCompleteTree(binaryTree.root));



    }


}